Hamiltonian Path

定义 Definition

哈密顿路径：在图论中，一条经过图中每个顶点恰好一次的路径（不要求回到起点）。若还要求首尾相连形成回路，则称为 Hamiltonian cycle（哈密顿回路）。

发音 Pronunciation (IPA)

/həˌmɪlˈtoʊniən pæθ/

例句 Examples

A Hamiltonian path visits every vertex exactly once.
哈密顿路径会把每个顶点恰好访问一次。

Finding a Hamiltonian path in a large graph can be computationally difficult.
在大型图中寻找一条哈密顿路径在计算上可能很困难。

词源 Etymology

“Hamiltonian” 来自爱尔兰数学家 William Rowan Hamilton（威廉·罗恩·哈密顿） 的姓氏；“path” 意为“路径”。该术语用于图论中描述一种“覆盖所有顶点且不重复”的路径概念（与“哈密顿回路”相关）。

相关词 Related Words

• Hamiltonian Cycle
• Graph
• Vertex
• Edge
• Cycle
• Eulerian Path
• NP-Complete
• Backtracking

文学与经典著作 Literary Works

• 《Graph Theory》（Bondy & Murty）——在讲解哈密顿图与相关路径/回路概念时使用该术语。
• 《Introduction to Graph Theory》（Douglas B. West）——系统讨论哈密顿路径、哈密顿回路及典型证明与例题。
• 《Computers and Intractability: A Guide to the Theory of NP-Completeness》（Garey & Johnson）——将哈密顿路径/回路作为经典 NP 完全问题的重要例子。